Pixel-based graphics systems define images on a display device by a two-dimensional, rectangular array of pixels. The discrete nature and finite number of such pixels can lead to visual artifacts such as jagged or staircase edges. These aliasing effects worsen for animated images where the jagged edges turn into crawling artifacts. Aliasing artifacts can occur when an entire pixel is given an intensity or color based upon an insufficient sample of points within that pixel, such as, for example, when a pixel is given either full intensity or no intensity, depending upon whether the image covers the center of the pixel.
To lessen or eliminate such jagged or crawling artifacts, the intensity of a pixel should not depend entirely upon whether the image covers a single point in the pixel. Accordingly, a variety of antialiasing techniques base the intensity of a pixel on more than that pixel's center. One such technique uses filters. Filters determine the intensity of each pixel by averaging data from a small area around that pixel. The width of the filter determines the area around the pixel that is included within the averaging, and a filter function is a weighting function applied to the averaging. For example, a box filter gives equal weight to the entire area covered by the filter. More sophisticated filter functions, such as a conical function, for example, give more weight to the area near the center of a pixel than to the area farther away. In practice, such sophisticated filters have better high-frequency rejection than box filters and consequently produce better antialiased images.
A problem, however, is that determining the pixel area covered by a sophisticated filter function and performing the weighted averaging can be computationally expensive. This is especially true if this filtering must be performed using multiple sample points within or near a pixel each time the pixel is written. One pre-filtering technique, described by Satish Gupta and Robert F. Sproull in "Filtering Edges for Gray-Scale Displays", Proceedings of SIGGRAPH 81, pp. 1-5, 1981, attempts to mitigate the problem by using a table to store pre-computed intensity values. The technique uses the table to map distances of pixels from the center of the line to be antialiased into pixel intensities.
Properly antialiasing the endpoints of a line, however, has traditionally been a problem for such pre-filtering techniques. In order to determine intensities for pixels at the endpoints, the technique described by Gupta et al., for example, must compute the slope of the line to produce an index into a table that maps slopes into pixel intensities. As a result, special operations are required at the start and end of each line. Moreover, the table works only for lines with endpoints that have integer coordinates, and the size of the table would become impracticable for line endpoints that are specified with multiple bits of sub-pixel precision. Thus, some filtering implementations simply ignore the endpoints--but then the endpoints become sharply cut off and remain aliased.
As a result, there remains a need for a method and computer system that can effectively antialias lines, including the endpoints, without being computationally expensive.